package 算法.查找算法;

public class 分块查找 {
    public static void main(String[] args) {
         /*
            分块查找
            核心思想：
                块内无序，块间有序
            实现步骤：
                1.创建数组blockArr存放每一个块对象的信息
                2.先查找blockArr确定要查找的数据属于哪一块
                3.再单独遍历这一块数据即可
        */
        int[] arr={ 16,5,9,12, 21,18,
                    32,23,37,26,45,34,
                    50,48,61,52,73,66};
        //1.把数据进行分块
        //要分 18开根号 4.5个左右

        //创建3个块对象
        Block b1=new Block(21,0,5);
        Block b2=new Block(45,6,11);
        Block b3=new Block(73,12, 17);

        //定义数组用来管理3个块的对象(索引表)
        Block[] blockArr={b1,b2,b3};

        //定义一个变量用来记录要查找的元素
        int number=52;

        //调用方法,传递索引表,数组,要查找的元素
        int index = getIndex(blockArr, arr, number);
        System.out.println(index);
    }

    //利用分块查找的原理,查询number的索引
    private static int getIndex(Block[] blockArr, int[] arr, int number) {
        //1.确定number在哪一个块中
        int blockIndex=finIndexBlock(blockArr,number);
        //如果返回值为-1说明不在块中,该值比所有块的最大值都大.
        if (blockIndex==-1){return -1;}
        //2.在块中进行查找
        Block dui=blockArr[blockIndex];
        for (int i = dui.getStartIndex(); i<= dui.getEndIndex() ; i++) {
            if (arr[i]==number){return i;}
        }
        return -1;
    }

    private static int finIndexBlock(Block[] blockArr, int number) {
        //比较
        for (int i = 1; i < blockArr.length; i++) {
            if(number<=blockArr[i].getMax()){//不需要number>=blockArr[i-1].getMax()&&
                //因为块的max是从小到大的,所以是按照顺序进行比较的.
                return i;
            }
        }
        return -1;//返回-1表示不存在
    }
}
class Block{
    private int max;//元素的最大值
    private int startIndex;//元素的开始索引
    private int endIndex;//元素的结束索引

    public Block() {
    }

    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
}